package dp.test132;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/23 9:35
 */
public class Solution1 {

    public int minCut(String s) {

        // 首先创建动态规划的辅助数组， dp[i]表示以 0 - i 的字符串的最小分割次数
        int[] dp = new int[s.length()];
        int n = s.length();

        // 初始化dp数组
        for (int i = 0; i < n; i++) {
            dp[i] = i;
        }

        for (int i = 0; i < n; i++) {
            int j = 0;
            while (true) {
                if (i - j < 0 || i + j >= n) {
                    break;
                }
                if (s.charAt(i - j) == s.charAt(i + j)) {
                    if (i - j == 0) {
                        // 走到边界了
                        dp[i + j] = 0;
                    } else {
                        dp[i + j] = Math.min(dp[i + j], dp[i - j - 1] + 1);
                    }
                } else {
                    break;
                }
                j++;
            }

            // 在考虑一下字符串是偶数的情况下
            j = 1;
            while (true) {
                if (i - j + 1 < 0 || i + j >= n) {
                    break;
                }
                if (s.charAt(i - j + 1) == s.charAt(i + j)) {
                    if (i - j + 1 == 0) {
                        dp[i + j] = 0;
                    } else {
                        dp[i + j] = Math.min(dp[i + j], dp[i - j] + 1);
                    }
                } else {
                    break;
                }
                j++;
            }
        }
        return dp[n - 1];
    }
}
